/*
*
==============================================================================
*  Name        : OmenOctree.cpp
*  Part of     : Omen Game Engine
*  Description : Implementation of OctreeNode and Octree classes
*  Version     : 1.0
*
*  Copyright (c) 2013 Lauri Kortevaara.
* 
==============================================================================
*/

#define OMEN_SOURCE 1

/// Omen Headers
#include "OmenOctree.h"

using namespace Omen;

/// STL Headers
#include <algorithm>
#include <iostream>

OctreeNode::OctreeNode() :
    m_bIsLeafNode(false),
    m_boundingBox( Vector3d(0.0,0.0,0.0),Vector3d(0.0,0.0,0.0) )
{
    memset( m_children, 0, 8*sizeof(IOctreeNode*) );
}

OctreeNode::OctreeNode( const OctreeNode& other ) :
    m_bIsLeafNode(other.m_bIsLeafNode),
    m_boundingBox(other.m_boundingBox)
{
    memcpy( m_children, other.m_children, 8*sizeof(IOctreeNode*) );
}

OctreeNode::~OctreeNode()
{
    for( int i=0; i < 8; ++i )
    if( m_children[i] )
    {
        delete m_children[i];
        m_children[i] = NULL;
    }
}

/// <summary>Returns reference to bounding box of this node</summary>
Omen::AABB& OctreeNode::boundingBox()
{
    return m_boundingBox;
}

/// <summary>Sets the bounding box of this node</summary>
void OctreeNode::setBoundingBox( const Omen::AABB& boundingBox )
{
    m_boundingBox = boundingBox;
}

/// <summary>Returns pointer to the 8 child nodes</summary>
IOctreeNode** OctreeNode::children()
{
    return reinterpret_cast<IOctreeNode**>(m_children);
}

/// <summary>Returns true if this node is a leaf node</summary>
bool OctreeNode::leaf() const
{
    return m_bIsLeafNode;
}

/// <summary>Get the faces contained in this node</summary>
void OctreeNode::getFaces( Omen::IMesh::Face** pListFaces, unsigned long maxSize )
{
    if( pListFaces )
    {
        maxSize = min(maxSize,m_listFaces.size());
        for( unsigned long i = 0; i < maxSize; ++i )
        {
            pListFaces[i] = m_listFaces.at(i);
        }
    }
}

/// <summary>In case this is a leaf node, return the number of faces contained in this node, otherwise 0</summary>
unsigned long OctreeNode::faceCount()
{
    return m_listFaces.size();
}


Octree::Octree() :
    m_maximumDepth(0),
    m_minimumCount(0),
    m_pRootNode(NULL)
{

}

Octree::Octree( const Octree& other )
{
}

Octree::~Octree()
{
}

IOctreeNode* Octree::rootNode() const
{
    return m_pRootNode;
}

void Octree::setRootNode( IOctreeNode* pRootNode )
{
    m_pRootNode = pRootNode;
}

/// <summary>Returns the maximum depth set for this octree</summary>
unsigned int Octree::maxDepth() const
{
    return m_maximumDepth;
}

/// <summary>Returns the minimum element count (object,mesh,face) that is used to stop the creation the octree in depth</summary>
unsigned int Octree::minimumFaceCount() const
{
    return m_minimumCount;
}

void Omen::OctreeNode::addFace( Omen::IMesh::Face* pFace )
{
    m_listFaces.push_back( pFace );
}

unsigned int Omen::OctreeNode::depth() const
{
    return m_depth;
}

void Omen::OctreeNode::subDivide( unsigned int treeDepth, std::vector<Omen::IMesh::Face*>& listFaces, unsigned int maximumDepth, unsigned int minimumFaceCount )
{
    if( listFaces.empty() )
        for( unsigned int i=0; i < m_listFaces.size(); ++i )
            listFaces.push_back(m_listFaces.at(i));

    if( treeDepth < maximumDepth )
    {
        // Create the child nodes
        for( unsigned int iChild = 0; iChild < 8; ++iChild )
        {
            m_children[iChild] = new Omen::OctreeNode;
            m_children[iChild]->m_depth = treeDepth;
        }

        Omen::Vector3d min = m_boundingBox.minimum();
        Omen::Vector3d max = m_boundingBox.maximum();
        
        Omen::Vector3d center = (max+min) / 2.0f;
        Omen::Vector3d extent = ((max-min) / 2.0f);

        // Create the child nodes

        // front top-left
        m_children[0]->m_boundingBox = Omen::AABB(center-Vector3d(extent.x,0,extent.z), center+Vector3d(0,extent.y,0));
        // front top-right
        m_children[1]->m_boundingBox = Omen::AABB(center-Vector3d(0,0,extent.z), center+Vector3d(extent.x,extent.y,0));

        // back top-left
        m_children[2]->m_boundingBox = Omen::AABB(center-Vector3d(extent.x,0,0), center+Vector3d(0.0,extent.y,extent.z));
        // back top-right
        m_children[3]->m_boundingBox = Omen::AABB(center, center+Vector3d(extent.x,extent.y,extent.z));
    
        // front bottom-left
        m_children[4]->m_boundingBox = Omen::AABB(center-Vector3d(extent.x,extent.y,extent.z), center);
        // front bottom-right
        m_children[5]->m_boundingBox = Omen::AABB(center-Vector3d(0,extent.y,extent.z), center+Vector3d(extent.x,0,0));
        // back bottom-left
        m_children[6]->m_boundingBox = Omen::AABB(center-Vector3d(extent.x,extent.y,0), center+Vector3d(0,0,extent.z));
        // back bottom-right
        m_children[7]->m_boundingBox = Omen::AABB(center-Vector3d(0,extent.y,0), center+Vector3d(extent.x,0.0,extent.z));

        // Divide the existing faces to sub AABBs
        std::vector<Omen::IMesh::Face*> listRemovedFaces;
        
        for( unsigned long faceI = 0; faceI < listFaces.size(); ++faceI )
        {
            Omen::IMesh::Face* pFace = listFaces.at(faceI);
            if( !pFace )
                continue;
                
            unsigned long p1 = pFace->p1;
            unsigned long p2 = pFace->p2;
            unsigned long p3 = pFace->p3;

            std::vector<Omen::IMesh::Vertex>::iterator v1, v2, v3;
            pFace->pParentMesh->getVertex(p1,v1);
            pFace->pParentMesh->getVertex(p2,v2);
            pFace->pParentMesh->getVertex(p3,v3);

            /*std::cout << "Face #" << faceI << std::endl << "v1[" << v1->x << "," << v1->y << "," << v1->z << "]" << std::endl \
                                                        << "v2[" << v2->x << "," << v2->y << "," << v2->z << "]" << std::endl \
                                                        << "v3[" << v3->x << "," << v3->y << "," << v3->z << "]" << std::endl << std::endl;*/
                
            bool faceAdded = false;
            for( unsigned int iChild = 0; iChild < 8; ++iChild )
            {
                Vector3d min = m_children[iChild]->boundingBox().minimum();
                Vector3d max = m_children[iChild]->boundingBox().maximum();
                
                Omen::Float bias = 0.7f;
                // Is the face parially inside the sub AABB, and if so, add this face to the sub-AABB
                if( (
                    (v1->x+bias) >= m_children[iChild]->boundingBox().minimum().x &&
                    (v1->x-bias) <= m_children[iChild]->boundingBox().maximum().x &&
                    (v1->y+bias) >= m_children[iChild]->boundingBox().minimum().y &&
                    (v1->y-bias) <= m_children[iChild]->boundingBox().maximum().y &&
                    (v1->z+bias) >= m_children[iChild]->boundingBox().minimum().z &&
                    (v1->z-bias) <= m_children[iChild]->boundingBox().maximum().z
                    ) 
                    &&
                    (
                    (v2->x+bias) >= m_children[iChild]->boundingBox().minimum().x &&
                    (v2->x-bias) <= m_children[iChild]->boundingBox().maximum().x &&
                    (v2->y+bias) >= m_children[iChild]->boundingBox().minimum().y &&
                    (v2->y-bias) <= m_children[iChild]->boundingBox().maximum().y &&
                    (v2->z+bias) >= m_children[iChild]->boundingBox().minimum().z &&
                    (v2->z-bias) <= m_children[iChild]->boundingBox().maximum().z
                    ) 
                    &&
                    (
                    (v3->x+bias) >= m_children[iChild]->boundingBox().minimum().x &&
                    (v3->x-bias) <= m_children[iChild]->boundingBox().maximum().x &&
                    (v3->y+bias) >= m_children[iChild]->boundingBox().minimum().y &&
                    (v3->y-bias) <= m_children[iChild]->boundingBox().maximum().y &&
                    (v3->z+bias) >= m_children[iChild]->boundingBox().minimum().z &&
                    (v3->z-bias) <= m_children[iChild]->boundingBox().maximum().z
                    ) )
                {
                    /*std::cout << "AABB #" << iChild << std::endl << "min[" << min.x << "," << min.y << "," << min.z << "]" << std::endl \
                                                                 << "max[" << max.x << "," << max.y << "," << max.z << "]" << std::endl << std::endl;
                    std::cout << "YEAH, It was fit!" << std::endl;*/
                    // If this face has not been already added to the removed face list, add it
                    if( std::find( listRemovedFaces.begin(), listRemovedFaces.end(), pFace ) == listRemovedFaces.end() )
                        listRemovedFaces.push_back(pFace);
                    m_children[iChild]->addFace(pFace);
                    faceAdded = true;
                }
                else
                {
                    //std::cout << "Did not fit!" << std::endl;
                }
            }

            if( !faceAdded )
            {
                //std::cout << "Face was not added!" << std::endl;
            }
        }

        // Now remove the faces that have been added to the sub-nodes
        while( !listRemovedFaces.empty() )
        {
            Omen::IMesh::Face* pFace = listRemovedFaces.back();
            listRemovedFaces.pop_back();
            // If this node has the face which has been added to sub-node, remove it from this node
            auto iter = std::find(m_listFaces.begin(), m_listFaces.end(), pFace );
            if( iter != m_listFaces.end() )
            {
                m_listFaces.erase( iter );
            }
            iter = std::find(listFaces.begin(), listFaces.end(), pFace );
            if( iter != listFaces.end() )
                listFaces.erase(iter);
        }

        // Make sure that all faces given to the function have been added to one of the sub-nodes
        /*if( !listFaces.empty() )
            std::wcout << L"Omen::Octree: Warning! Not all of the face were added to octree!" << std::endl;*/

        // Then sub divide
        for( unsigned int iChild = 0; iChild < 8; ++iChild )
        {
            if( m_children[iChild]->faceCount() == 0 )
            {
                delete m_children[iChild];
                m_children[iChild] = NULL;
            }
        }
        for( unsigned int iChild = 0; iChild < 8; ++iChild )
        {
            if( !m_children[iChild] )
                continue;
            else
               m_children[iChild]->subDivide( treeDepth+1, listFaces, maximumDepth, minimumFaceCount );
        }
    }
}

/// <summary>Octree creation function, called from the IOmenFactory::createOctree. Declared in IOmenOctree.h </summary>
Omen::IOctree* createOctree( const Omen::IScene* pScene, unsigned int maximumDepth, unsigned int minimumFaceCount )
{
    Omen::Octree* pOctree = NULL;

    /// Check that there are models in the scene
    unsigned long modelCount = pScene->modelCount();
    if( modelCount )
    {
        /// Create the new octree object
        pOctree = new Omen::Octree();
        std::vector<Omen::IMesh::Face*> listFaces; // Contains all faces in the scene

        Omen::AABB aabb( Omen::Vector3d(0.0,0.0,0.0), Omen::Vector3d(0.0,0.0,0.0) );

        // Get the models in the scene
        Omen::IModel** pModelList = new Omen::IModel*[modelCount];
        if( pModelList )
        {
            pScene->getModels(pModelList, modelCount);

            // Start creating the octree
            for( unsigned long iModel=0; iModel < modelCount; ++iModel )
            {
                Omen::IModel* pModel = pModelList[iModel];
                if( pModel )
                {
                    pModel->updateBoundingVolume();
                    aabb = aabb + pModel->boundingBox();
                    unsigned long meshCount = pModel->meshCount();
                    Omen::IMesh** pMeshList = new Omen::IMesh*[meshCount];
                    if( pMeshList )
                    {
                        pModel->getMeshes(pMeshList,meshCount);
                        for( unsigned long iMesh=0; iMesh < meshCount; ++iMesh )
                        {
                            Omen::IMesh* pMesh = pMeshList[iMesh];
                            if( pMesh )
                            {
                                unsigned long faceCount = pMesh->faceCount();
                                Omen::IMesh::Face** pFaceList = new Omen::IMesh::Face*[faceCount];
                                if( pFaceList )
                                {
                                    pMesh->getFaces( pFaceList, faceCount );
                                    /// Add all faces in the mesh to the global list of faces for octree generation
                                    for( unsigned long iFace = 0; iFace < faceCount; ++iFace )
                                        listFaces.push_back(pFaceList[iFace]);
                                    delete[] pFaceList;
                                }
                            }
                        }
                        delete[] pMeshList;
                    }
                }
            }
            // Releae the list of model pointers
            delete[] pModelList;
        }

        Omen::Float minX = aabb.minimum().x;
        Omen::Float minY = aabb.minimum().y;
        Omen::Float minZ = aabb.minimum().z;
        Omen::Float maxX = aabb.maximum().x;
        Omen::Float maxY = aabb.maximum().y;
        Omen::Float maxZ = aabb.maximum().z;
        std::cout << "RootNode Minimum aabb : (" << minX << ", " << minY << ", " << minZ << ")" << std::endl;
        std::cout << "RootNode Maximum aabb : (" << maxX << ", " << maxY << ", " << maxZ << ")" << std::endl;

        Omen::OctreeNode* pRootNode = new Omen::OctreeNode;
        if( pRootNode )
        {
            pOctree->setRootNode(pRootNode);
            pRootNode->setBoundingBox(aabb);
            pRootNode->subDivide( 0, listFaces, maximumDepth, minimumFaceCount );
        }
    }
    return pOctree;
}

/// EOF
